import { _Array } from './Array'

export class MaxHeap {
    constructor(data = null) {
        this.data = new _Array()

        if (data) {
            this.data = new _Array(0, data)
            for (let i = this._parent(data.length - 1); i >= 0; i--) {
                this._siftDown(i)
            }
        }
    }

    getSize() {
        return this.data.getSize()
    }

    isEmpty() {
        return this.data.isEmpty()
    }

    _parent(index) {
        if (index === 0) {
            throw new Error('index-0 does not have parent.')
        }
        return Math.floor((index - 1) / 2)
    }

    _leftChild(index) {
        return index * 2 + 1
    }

    _rightChild(index) {
        return index * 2 + 2
    }

    add(e) {
        this.data.addLast(e)
        this._siftUp(this.data.getSize() - 1)
    }

    _siftUp(index) {
        // 比较是否比父节点的值小
        while (index > 0 && this.data.get(this._parent(index)) < this.data.get(index)) {
            this.data.swap(index, this._parent(index))
            index = this._parent(index)
        }
    }

    findMax() {
        if (this.data.getSize() === 0) {
            throw new Error('Can not findMax when heap is empty.')
        }

        return this.data.get(0)
    }

    extractMax() {
        const max = this.findMax()

        this.data.swap(0, this.data.getSize() - 1)
        this.data.removeLast()
        this._siftDown(0)

        return max
    }

    _siftDown(index) {
        // 左子节点的索引越界
        while (this._leftChild(index) < this.data.getSize()) {
            let lc = this._leftChild(index)

            if (lc + 1 < this.data.getSize() && this.data.get(lc + 1) > this.data.get(lc)) {
                lc = this._rightChild(index)
            }

            if (this.data.get(index) >= this.data.get(lc)) {
                break
            }

            this.data.swap(index, lc)
            index = lc
        }
    }

    replace(e) {
        const max = this.findMax()
        this.data.set(0, e)
        this._siftDown(0)
        return max
    }

}